package graph.unweighted.dfs.loopDetection;

import graph.unweighted.CandyGraph;

/**
 * 
 * @Title: LoopDetect.java 
 * @Package graph.dfs.demo3 
 * @Description: 使用DFS完成对无向图的环检测
 * @author CandyWall   
 * @date 2021年1月15日 下午1:26:00 
 * @version V1.0
 */
public class CandyLoopDetection {
    private CandyGraph graph;
    private boolean[] visited;  //记录顶点是否被遍历过，默认都为false
    public CandyLoopDetection(CandyGraph graph) {
        if(graph.isDirected()) {
            throw new IllegalArgumentException("该类只能对无向图进行环检测！");
        }
        this.graph = graph;
        visited = new boolean[graph.getVertex_num()];
        // System.out.println("当前树是否有环：" + hasLoop());
    }
    
    /**
     * 判断当前图中是否有环
     * @return
     */
    public boolean hasLoop() {
        for(int v = 0; v < graph.getVertex_num(); v++) {
            if(!visited[v]) {
                if(dfs(v, v)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    /**
     * 计算当前图中环的数量：需要在dfs的else if中添加条件：v != prev，
     * 否则，可能会在第一次递归的时候检测到假环
     * @return
     */
    public int getLoopCount() {
        int count = 0;
        for(int v = 0; v < graph.getVertex_num(); v++) {
            if(!visited[v]) {
                if(dfs(v, v)) {
                    count++;
                }
            }
        }
        return count;
    }
    /**
     * 深度优先遍历：从顶点v出发，判断图中是否有环
     */
    private boolean dfs(int v, int prev) {
        visited[v] = true;
        for(int w : graph.adjacentVertexes(v)) {
            if(!visited[w]) {
                if(dfs(w, v)) {
                    return true;
                }
            }
            // 如果遍历过了，并且不是当前节点的上一个节点
            else if(w != prev && v != prev) {
                return true;
            }
        }
        return false;
    }
    
    public static void main(String[] args) {
        CandyGraph graph1 = new CandyGraph("testData/graph/graph.txt");
        CandyLoopDetection loopDetect1 = new CandyLoopDetection(graph1);
        System.out.println("当前图中环的数量：" + loopDetect1.getLoopCount());
        CandyGraph graph2 = new CandyGraph("testData/graph/dfs/demo3/graph.txt");
        CandyLoopDetection loopDetect2 = new CandyLoopDetection(graph2);
        System.out.println("当前图中环的数量：" + loopDetect2.getLoopCount());
        // 无向图环检测
        CandyGraph graph3 = new CandyGraph("testData/directed/loopDetection/Graph1.txt", true);
        CandyLoopDetection loopDetect3 = new CandyLoopDetection(graph3);
        System.out.println("当前图中环的数量：" + loopDetect3.getLoopCount());
    }
}
